/*
 * @lc app=leetcode id=147 lang=cpp
 *
 * [147] Insertion Sort List
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {

        if (!head || !head->next) {
            return head;
        }

        ListNode *fakeHead = new ListNode(0);
        fakeHead->next = head;

        ListNode *node = NULL;
        ListNode *sortedNode = head;
        while (sortedNode->next) {
            node = fakeHead;

            while (node->next != sortedNode->next && 
                    node->next->val < sortedNode->next->val) {
                node = node->next;
            }

            if (node->next != sortedNode->next) {
                ListNode *tmp = sortedNode->next;
                sortedNode->next = tmp->next;
                tmp->next = node->next;
                node->next = tmp;
            } else {
                sortedNode = sortedNode->next;
            }
        }
        
        head = fakeHead->next;
        delete fakeHead;
        return head;
    }
};

